package top.humbleyuan.others;

import java.util.Arrays;

/**
 * @Author: yuanhuanghui
 * @Date: 2020-08-07
 * @Time: 15:33
 * @Description: 下一个字典序排列
 */
public class LeetCode_31 {
    public static void main(String[] args) {
        int[] nums = {1, 3, 2};
        if(nums == null) {
            return;
        }

        /**
         1. 从后往前先找到第一个升序的index
         2. 此时index之后的数必然降序
         3. 再从后面找刚好比nums[index]大的数，与之交换(这个可以由条件2保证)
         4. 此时完成前面的小数和后面刚好比他大的数交换
         5. 交换之后，后面的数为降序，需要改为升序
         **/
        int i;
        for(i = nums.length - 1; i >= 1; i--) {
            if(nums[i] > nums[i - 1]) {
                break;
            }
        }

        // 全局降序，直接逆序
        if(i == 0) {
            reverse(nums, 0);
            return;
        }

        // 注意i的位置
        i--;
        int j;
        for(j = nums.length - 1; j > i;j--) {
            if(nums[j] > nums[i]) {
                swap(i, j, nums);
                break;
            }
        }

        // 此时j往后是降序，需要最小，变为升序
        reverse(nums, i + 1);
        System.out.println();
    }

    public static void reverse(int[] nums, int start) {
       int end = nums.length - 1;
       while (start < end) {
           swap(start, end, nums);
           start++;
           end--;
       }
    }

    public static void swap(int n, int m, int[] nums) {
        int temp = nums[n];
        nums[n] = nums[m];
        nums[m] = temp;
    }
}
